package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * 题目1：后继节点：
 * 1.后继节点是指在中序遍历中，排在当前节点后面的那个节点
 * *   A
 * *  B C
 * * DE FG
 * 中序：D B E A F C G
 * 1.如果当前节点有右子树，则返回右子树中最左边的节点
 * 2.如果当前节点没有右子树，则向上遍历父节点，直到找到一个父节点，其左子节点是当前节点。
 * <p>
 * https://leetcode.cn/problems/successor-lcci/
 * 题目2：求有搜索二叉树的有序节点
 */
public class Code15_SuccessorNode {
    public static void main(String[] args) {
        /**
         *          6
         *        /   \
         *       3     9
         *      / \   / \
         *     1  4  8 10
         *      \  \
         *       2  5
         *      /
         *     7
         */
        TreeNode head = new TreeNode(6);
        head.parent = null;
        head.left = new TreeNode(3);
        head.left.parent = head;
        head.left.left = new TreeNode(1);
        head.left.left.parent = head.left;
        head.left.left.right = new TreeNode(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new TreeNode(4);
        head.left.right.parent = head.left;
        head.left.right.right = new TreeNode(5);
        head.left.right.right.parent = head.left.right;
        head.right = new TreeNode(9);
        head.right.parent = head;
        head.right.left = new TreeNode(8);
        head.right.left.parent = head.right;
        head.right.left.left = new TreeNode(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new TreeNode(10);
        head.right.right.parent = head.right;
        TreeNode test1 = head.left.left;

        TreeNode successorNode1 = getSuccessorNode(test1);
        System.out.println(successorNode1);
        TreeNode test2 = head.left.right.right;
        TreeNode successorNode2 = getSuccessorNode(test2);
        System.out.println(successorNode2);

    }

    // 题目1：带parent的后继节点
    public static TreeNode getSuccessorNode(TreeNode node) {
        if (node == null) {
            return node;
        }

        // 如果右子树不为空
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            TreeNode parent = node.parent;
            // 需要向上遍历父节点，直到找到一个父节点，其左子节点是当前节点。这个父节点就是后继节点。
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    // 题目2：搜索二叉树的后继节点
    public static TreeNode getSuccessorNode(TreeNode node, TreeNode p) {
        if (p == null) {
            return p;
        }
        // 存在右节点的后继方式，与题目1相同
        if (p.right != null) {
            return getLeftMost(p.right);
        } else {
            // 而搜索二叉树，则需要遍历
            // cur 从根节点 node 开始遍历。
            // ans 用于记录可能的后继节点，初始为 null。
            TreeNode cur = node, ans = null;
            while (cur != null) {
                // 如果当前节点 cur 的值大于 p 的值，
                // 说明 p 的后继节点可能在 cur 的左子树中，因此将 ans 更新为 cur，并继续向左子树遍历。
                if (cur.val > p.val) {
                    ans = p;
                    cur = cur.left;
                } else {
                    // 如果当前节点 cur 的值小于或等于 p 的值，
                    // 说明 p 的后继节点可能在 cur 的右子树中，因此继续向右子树遍历。
                    cur = cur.right;
                }
            }
            // 遍历结束后，ans 就是 p 的中序后继节点。
            return ans;
        }
    }


    // 返回最左子节点
    private static TreeNode getLeftMost(TreeNode treeNode) {
        if (treeNode == null) {
            return treeNode;
        }
        while (treeNode.left != null) {
            treeNode = treeNode.left;
        }
        return treeNode;
    }

}
